package com.sali.排序;

/**
 数组中的逆序对
 */
public class JZ_51 {

    int MOD = 1000000007;

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int InversePairs (int[] nums) {
        int[] numsCopy = new int[nums.length];
        System.arraycopy(nums, 0, numsCopy, 0, nums.length);
        return getRes(nums, numsCopy, 0, nums.length - 1);
    }

    private int getRes(int[] nums, int[] numsCopy, int left, int right) {
        if ( left >= right ) {
            return 0;
        }
        int mid = left + (right - left) / 2;
        int count = 0;
        count = ( count + getRes(nums, numsCopy, left, mid)) % MOD;
        count = ( count + getRes(nums, numsCopy, mid + 1, right)) % MOD;
        count = ( count + myMerge(nums, numsCopy, left, mid, right)) % MOD;
        return count;
    }

    private int myMerge(int[] nums, int[] numsCopy, int left, int mid, int right) {
        int leftPoint = left;
        int rightPoint = mid + 1;
        int index = left;
        int count = 0;
        while ( leftPoint <= mid && rightPoint <= right ) {
            if ( nums[leftPoint] <= nums[rightPoint] ) {
                numsCopy[index++] = nums[leftPoint++];
            } else {
                count = ( count + mid - leftPoint + 1 ) % MOD;
                numsCopy[index++] = nums[rightPoint++];
            }
        }
        while ( leftPoint <= mid ) {
            numsCopy[index++] = nums[leftPoint++];
        }
        while ( rightPoint <= mid ) {
            numsCopy[index++] = nums[rightPoint++];
        }
        for ( int i = left; i <= right; i++ ) {
            nums[i] = numsCopy[i];
        }
        return count;
    }

}
